/*
** extend_gcd.c
** 
** Made by (seakage2h)
** Login   <seakage2h@seakage2h-ubuntu>
** 
** Started on  Thu Mar 19 10:52:58 2009 seakage2h
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

#include <stdio.h>

int main(int argc, char* argv[])
{
    int x = 1, y, g, v = 0, w, s, t, q, a, b;

    a = atoi(argv[1]);
    b = atoi(argv[2]);

    if (b > a){
        s = a;
        a = b;
        b = s;
    }

    g = a, w = b;
    
    while(w){
        q = g / w;
        t = g % w;
        s = x - q * v;
        x = v, g = w;
        v = s, w = t;
    }

    y = (g - a * x) / b;

    printf("a = %d,\t b = %d,\t GCD: %d,\nx = %d,\ty = %d\n", a, b, g, x, y);

    return 0;
}

